\subsection{Local Search}

We have implemented various versions of local search to solve the problem. They
have a common run time that we will analyze in the following. The local search we
have implemented have the form described in Fig. \ref{fig:localSearch}.

\begin{figure}[h] 

  \centering \begin{algorithmic} 

    \STATE \textbf{PROCEDURE} LocalSearch(Assignment $A$,Temperature $T$) \textbf{returns} Assignment:
    
    \STATE let $N \leftarrow$ a neighbor of $A$ chosen uniformly at random.
    
    
    \IF{$C(N)\leq C(A)$}
    \STATE $A \leftarrow N$
         
    \ELSE
    \STATE With probability  $T$,  $A \leftarrow N$.
    \STATE Otherwise, leave $A$ unchanged.    
    
    \ENDIF
    
    \RETURN{$A$}
  \end{algorithmic} 

  \caption{One local search step.}
  \label{fig:localSearch} 
\end{figure} 

The first costly operation is the cost of finding a random neighbor. In section 
\ref{subsubsec:neighborhood} we discussed methods for finding good neighbors
and the size of the neighborhood was discussed. For local search we don't want
to explorer the entire neighborhood, but rather just pick a neighbor at
random. The process is similar to the a algorithm outlined in
Fig. \ref{fig:neighbor} for finding the neighborhood, but there is no need to
iterate across days and type as we can choose theses at random. Thus the work
for generating a random neighbor can be described as:

\begin{enumerate}
	\item Picking a random day and type (constant in input)
	\item Picking departments to distribute from and to (A few runs over the input, or picking at random at constant cost)
	\item Cloning the current assignment. (One iteration over the input)
	\item adding and subtracting values. (A few runs over the input)  
\end{enumerate}

So the run-time of generating a random neighbor totals a few iterations over the
input $\sim 3n$. The next step in the local search is determining the cost of
the original $A$ and the neighboring $N$ assignments. The run time for finding the
assignment cost was found in Eq. \ref{eq:cost-c-final}. Doing it two times gives
a total of $\sim 244n$. The last few operations are mathematical operations that
are constant in the input-size. All in all the estimated cost of running one
local search step is $\sim 247n$ which is $O(n)$. The algorithm scales linearly
and thus allows thousands of iterations to be executed in minutes on a modern
PC.
 
 
